package com.kaifamiao.month04.day12;

import java.util.Arrays;

/**
 * 找到字符串中最长的回文子串
 * <p>
 * 回文字符串: 正序、倒序一致 eg: aba  abba
 * 子串： 字符串 abcd 中子串： abc bcd ab bc cd (连续)
 * <p>
 * 输入： abcdefedcaca
 * 输出： cdefedc
 * <p>
 * 输入： abccba
 * 输出： abccba
 */
public class Homework {

    /**
     * 实现方法一 查找字符串中的最长回文子串
     *
     * @param str 需要寻找的字符串
     * @return 最长回文子串
     */
    public static String palindrome(String str) {
        String newStr = "";
        for (int i = str.length(); i >= 0; i--) {
            for (int j = 0; i - j <= str.length() && j <= i; j++) {
                String child = str.substring(j, i);
                if (isPalindrome(child)) {
                    newStr = child.length() >= newStr.length() ? child : newStr;
                }
            }
        }

        return newStr;
    }

    public static String palindrome2(String str) {
        StringBuilder newStr = new StringBuilder("");
        String maxLengthStr = "";
        for (int i = 0; i < str.length(); i++) {
            String current = Character.toString(str.charAt(i));
            if (newStr.toString().contains(current)) {
                newStr.append(current);
                int index = newStr.indexOf(current);
                int lastIndex = newStr.lastIndexOf(current);
                if (isPalindrome(newStr.substring(index, lastIndex).toString())) {
                    maxLengthStr = newStr.length() >= maxLengthStr.length() ? newStr.toString() : maxLengthStr;
                    newStr = new StringBuilder("");
                }
            } else {
                newStr.append(current);
            }
        }
        return maxLengthStr;
    }

    public static String palindrome3(String str) {
        String[] newStrings = new String[str.length()];
        int count = 0;
        String newStr = "";
        for (int i = 0; i < str.length(); i++) {
            int index = str.indexOf(str.charAt(i));
            int lastIndex = str.indexOf(str.charAt(i), index + 1);
            if (index != lastIndex && lastIndex != -1) {
                newStr = str.substring(index, lastIndex + 1);
                if (isPalindrome(newStr)) {
                    newStrings[count++] = newStr;
                }
            }
        }
        return count == 0 ? str.charAt(0) + "" : maxLengthStr(Arrays.copyOf(newStrings, count));
    }

    // 检测是否是回文字符
    private static boolean isPalindrome(String str) {
        StringBuilder newStr = new StringBuilder(str); // StringBuilder 在单线程情况比 StringBuffer 运行快
        return str.equals(newStr.reverse().toString());
    }

    // 找出最长的数组元素
    private static String maxLengthStr(String[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j].length() > arr[j + 1].length()) {
                    String temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        return arr[arr.length - 1];
    }

    public static String palindrome4(String s) {
        String res = "";
        for (int i = 0; i < s.length(); i++) {
            String s1 = getPalindrome(s, i, i); // 以 i 下标为中心的最长回文子串
            String s2 = getPalindrome(s, i, i + 1); // 以 i 和 i+1 为中心的最长回文子串
            res = res.length() > s1.length() ? res : s1;
            res = res.length() > s2.length() ? res : s2;
            if (res.length() >= (s.length() - i) * 2 ) {
                break;
            }
        }
        return res;
    }

    private static String getPalindrome(String s, int l, int r) {
        // 防止索引越界
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            // 向两边展开
            l--;
            r++;
        }
        return s.substring(l + 1, r); // 返回以 l 和 r 为中心的最长回文串
    }

    public static void main(String[] args) {
        String str = "abcdefedcaca";
        System.out.println(palindrome4(str));
    }

}

